class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left=-1,i=0;                                //    0          1            ?           2
        int right=nums.size();                   // [0.left]  [left+1,i-1] [i,right-1] [right,n-1]
                                                    //nums[i]
        while(i<right)
        {
            if(nums[i]==0)
            {
                swap(nums[++left],nums[i++]);
            }
            else if(nums[i]==1) ++i;
            else
            {
                swap(nums[--right],nums[i]);
            }
        }
    }
};